// https://www.lintcode.com/problem/4sum/

public class Solution {
    /**
     * @param numbers: Give an array
     * @param target: An integer
     * @return: Find all unique quadruplets in the array which gives the sum of zero
     */
    public List<List<Integer>> fourSum(int[] numbers, int target) {
        // write your code here
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(numbers);
        kSum(ret, numbers, target, 0, 0, 4, new ArrayList<Integer>());
        return ret;
    }
    
    private void kSum(List<List<Integer>> ret, int[] numbers, int target, int sum, int start, int k, List<Integer> v) {
        if (k == 0) {
            if (sum == target) {
                List<Integer> _v = new ArrayList<>();
                for (Integer i : v) {
                    _v.add(i);
                }
                ret.add(_v);
            }
        } else if (start < numbers.length) {
            v.add(numbers[start]);
            kSum(ret, numbers, target, sum + numbers[start], start + 1, k - 1, v);
            v.remove(v.size() - 1);
            int i = start + 1;
            while ((i < numbers.length) && (numbers[i] == numbers[start])) {
                ++i;
            }
            kSum(ret, numbers, target, sum, i, k, v);
        }
    }
}